package 代码记录.校招笔试真题.笔试真题_2022;

/**
 * @author zx
 * @create 2022-09-05 21:59
 */
public class 正则表达式匹配 {
    public boolean isMatch(String s, String p) {
        //技巧：往原字符头部插入空格,这样得到char数组是从1开始,
        //可以使得f[0][0] = true,将true这个结果滚动下去
        int n = s.length(), m = p.length();
        s = " " + s;
        p = " " + p;
        char[] c1 = s.toCharArray();
        char[] c2 = p.toCharArray();
        //f(i,j)代表考虑s中的1 ~ i字符和p中的1 ~ j字符是否匹配
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果下一个字符是 '*',则代表当前字符不能被单独使用,跳过
                if (j + 1 <= m && c2[j + 1] == '*') {
                    continue;
                }
                // 对应了p[j]为普通字符和 '.' 的两种情况
                if (i - 1 >= 0 && c2[j] != '*') {
                    dp[i][j] = dp[i - 1][j - 1] && (c1[i] == c2[j] || c2[j] == '.');
                }
                // 对应了p[j] 为 '*' 的情况
                else if (c2[j] == '*') {
                    dp[i][j] = (j - 2 >= 0 && dp[i][j - 2]) || (i - 1 >= 0 && dp[i - 1][j] && (c1[i] == c2[j - 1] || c2[j - 1] == '.'));
                }
            }
        }
        return dp[n][m];
    }

    public boolean isMatch2(String A, String B) {
        int n = A.length();
        int m = B.length();
        boolean[][] f = new boolean[n + 1][m + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                //分成空正则和非空正则两种
                if (j == 0) {
                    f[i][j] = i == 0;
                } else {
                    //非空正则分为两种情况 * 和 非*
                    if (B.charAt(j - 1) != '*') {
                        if (i > 0 && (A.charAt(i - 1) == B.charAt(j - 1) || B.charAt(j - 1) == '.')) {
                            f[i][j] = f[i - 1][j - 1];
                        }
                    } else {
                        //碰到 * 了，分为看和不看两种情况
                        //不看
                        if (j >= 2) {
                            f[i][j] |= f[i][j - 2];
                        }
                        //看
                        if (i >= 1 && j >= 2 && (A.charAt(i - 1) == B.charAt(j - 2) || B.charAt(j - 2) == '.')) {
                            f[i][j] |= f[i - 1][j];
                        }
                    }
                }
            }
        }
        return f[n][m];
    }
}
